#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void merge_sort(int *a, int *b, int begin, int end);
void merge_pass(int *a, int *b, int len, int s);
void merge(int *a, int len);
void merge_sort(int *a, int *b, int begin, int end)
{
    int i = begin;
    int j = (begin + end) / 2 + 1;
    int k = begin;
    while((i <= (begin + end) / 2) && j <= end)
    {
        b[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    if(i <= (begin + end) / 2)
    {
        for(; i <= (begin + end) / 2; ++i)
        {
            b[k++] = a[i];
        }
    }
    else
    {
        for(; j <= end; ++j)
        {
            b[k++] = a[j];
        }
    }
}

void merge_pass(int *a, int *b, int len, int s)
{
    int i = 0;
    //assert(len >= s);
    while(i < len - 2*s)
    {
        merge_sort(a, b, i, i + 2 * s - 1);
        i += 2*s;
    }
    if(i + s < len)
    {
        merge_sort(a, b, i, len - 1);
    }
    else
    {
        for(; i < len; ++i)
        {
            b[i] = a[i];
        }
    }
}

void merge(int *a, int len)
{
    int b[sizeof(a)/sizeof(int)] = {0};
    int s = 1;
    while(s < len)
    {
        merge_pass(a,b,len,s);
        s += s;
        merge_pass(b,a,len,s);
        s += s;
    }
}
void output(int a[]) {
       int i;
       for(i = 0;i < 7;i++) printf("%d\t",a[i]);
       printf("\n");
}
int main(void) {
       int a[7] = {44, 12, 145, -123, -1, 0, 121};
       printf("-------------------------------merge sort----------------------------\n");
       output(a);
       merge(a, 7);
       output(a);
       return 0;
}
